package com.lz.sort;

/**
 * InsertSort..
 *
 * 思想： 假设前前面的已经排好序，取后面的与其比较，并插入，逐步往后移
 *
 * @author Lizhong
 * @date 2019/9/2
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] a = {12, 20, 5, 16, 15, 1, 30, 45, 5, 23, 9};
        method01(a);
        PrintUtil.printArray(a);
    }

    public static void insert(int[] items) {
        int length = items.length;
        for (int i = 1; i < length; i++) {
            int current = items[i];
            int j = i - 1;
            do {
                if (current < items[j]) {
                    items[j + 1] = items[j];// 后移
                } else {
                    break;
                }
                j--;
            } while (j >= 0);
            items[j + 1] = current; // 插入
        }
    }

    /**
     * 希维尔排序，快排的升级版
     * @param items
     */
    public static void shellSort(int[] items) {
        int length = items.length;
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) {
                int current = items[i];
                int j = i - step;
                do {
                    if (current < items[j]) {
                        items[j + step] = items[j];// 后移
                    } else {
                        break;
                    }
                    j -= step;
                } while (j >= 0);
                items[j + step] = current; // 插入
            }
        }
    }

    public static void method01(int t[]) {
        for (int i = 1; i < t.length; i++) {
            int current = t[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (current < t[j]) {
                    t[j + 1] = t[j];
                } else break;
            }
            t[j+1] = current;
        }
    }
}
